/*
 * @lc app=leetcode id=743 lang=cpp
 *
 * [743] Network Delay Time
 */
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<int> waits(N, INT_MAX);
        waits[K-1] = 0;
        unordered_map<int, unordered_map<int,int>> adj;

        for (auto& edge : times) {
            adj[edge[0]-1][edge[1]-1] = edge[2];
        }

        // sort by path
        auto comp = [](const std::pair<int,int>& lhs, const std::pair<int,int>& rhs) {
            return lhs.first > rhs.first;
        };
        priority_queue<std::pair<int, int>, std::vector<std::pair<int,int>>, decltype(comp)> pq(comp);
        pq.push({0, K-1});

        while (!pq.empty()) {
            auto& e = pq.top();
            int node = e.second;
            pq.pop();

            for (auto& edge : adj[node]) {

                int dest = edge.first;
                int dist = edge.second;

                if (waits[node] + dist < waits[dest]) {
                    waits[dest] = waits[node] + dist;
                    pq.push({waits[dest], dest});
                }
            }
        }

        int sum = 0;
        for (auto w : waits) {
            if (w == INT_MAX) {
                return -1;
            }

            sum = std::max(sum, w);
        }
        return sum;
    }
};

